package org.cxy.knapsack;

/**
 * 背包问题: 输出价值
 */
public class Knapsack01 {

    /**
     * 0-1 背包问题：返回最大价值
     * @param weights 物品重量数组
     * @param values  物品价值数组
     * @param W       背包最大承重
     * @return        能获得的最大价值
     */
    public static int knapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        // dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
        int[][] dp = new int[n + 1][W + 1];

        // 填表
        for (int i = 1; i <= n; i++) {
            int weight = weights[i - 1];
            int value = values[i - 1];
            for (int w = 0; w <= W; w++) {
                // 不选第 i-1 个物品
                dp[i][w] = dp[i - 1][w];

                // 如果能装下，尝试选择
                if (w >= weight) {
                    dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight] + value);
                }
            }
        }

        return dp[n][W];
    }

    // 测试
    public static void main(String[] args) {
        int[] weights = {1, 2, 3};
        int[] values  = {6, 10, 12};
        int W = 5;

        int maxValue = knapsack(weights, values, W);
        System.out.println("最大价值: " + maxValue); // 输出：22
    }
}